package 算法.字符串.单词查找树;

import com.sun.jndi.url.iiopname.iiopnameURLContextFactory;
import com.sun.org.apache.xerces.internal.impl.dv.dtd.NMTOKENDatatypeValidator;
import com.sun.swing.internal.plaf.metal.resources.metal;

import edu.princeton.cs.algs4.Queue;
import sun.awt.SunHints.Value;
import sun.security.util.Length;

/**
 * 【单词查找树：R向】
 * 		注：R为字符数
 * @Date 2017-09-04 19：39
 * @author Administrator
 * @version TODO:>>>>>>>尚未测试
 */
public class TrieST<Value> {
	private static final int R = 256; // 字符数：按照ASCII码
	private Node<Value> root;

	private static class Node<Val> {
		public Val val;
		public Node<Val>[] next = new Node[R];
	}

	public Value get(String k) {
		Node<Value> node = get(root, k, 0); // 从第一个字符开始搜索
		if (node == null)
			return null;
		return node.val;
	}

	/**
	 * get
	 * 
	 * @param x
	 * @param k
	 * @param offset
	 * @return
	 */
	public Node<Value> get(Node<Value> x, String k, int offset) {
		if (x == null)
			return null;
		if (offset == k.length())
			return x;
		char c = k.charAt(offset);
		return get(x.next[c], k, offset + 1);
	}

	public void put(String k, Value v) {
		root = put(root, k, v, 0);
	}

	/**
	 * put
	 * 
	 * @param x
	 * @param k
	 * @param v
	 * @param offset
	 * @return
	 */
	public Node<Value> put(Node<Value> x, String k, Value v, int offset) {
		if (x == null)
			x = new Node<Value>();
		if (offset == k.length()) {
			x.val = v;
			return x;
		}
		char c = k.charAt(offset); // 找到第offset个字符所对应的子单词查找树
		x.next[c] = put(x.next[c], k, v, offset + 1);
		return x;
	}

	/**
	 * keysWithPrefix() 找到所有以pre开头的单词
	 * 
	 * @param pre
	 * @return
	 */
	public Iterable<String> keysWithPrefix(String pre) {
		Queue<String> q = new Queue<>();
		Node<Value> node = get(root, pre, 0);
		collection(node, pre, q);
		return q;
	}

	public void collection(Node<Value> x, String pre, Queue<String> q) {
		if (x == null)
			return;
		if (x.val != null)
			q.enqueue(pre);
		for (int c = 0; c < R; c++)
			collection(x.next[c], pre + c, q);
	}

	/**
	 * keys()：遍历全树：得到所有单词
	 * 
	 * @return
	 */
	public Iterable<String> keys() {
		return keysWithPrefix("");
	}

	/**
	 * longestPrefixOf()：找到某个字符串的最长前缀键 eg：树中有"zou","zouc","zouch"这几个单词
	 * 传入str为"zouchao"：查询结果"zouch"
	 * 
	 * @param str
	 * @return
	 */
	public String longestPrefixOf(String str) {
		return str.substring(0, search(root, str, 0, 0));
	}

	public int search(Node<Value> x, String str, int offset, int length) {
		if (x == null)
			return length; // 返回上一次找到键的长度
		if (x.val != null)
			length = offset; // 找到更长的键，更新offset
		if (offset == str.length())
			return length; // 找到字符串
		char c = str.charAt(offset);
		return search(x.next[c], str, offset + 1, length);
	}

	/**
	 * 删除：
	 * 
	 * @param str
	 */
	public void delete(String str) {
		delete(root, str, 0);
	}

	public Node<Value> delete(Node<Value> x, String str, int offset) {
		if (x == null)
			return null;
		if (offset == str.length()) {
			x.val = null;
		} else {
			char c = str.charAt(offset);
			x.next[c] = delete(x.next[c], str, offset + 1);
		}
		if (x.val != null)
			return x;
		for (int c = 0; c < R; c++) {
			if (x.next[c] != null) {
				return x;
			}
		}
		return null;
	}

	/**
	 * 通配符：找到所有匹配的字符串
	 * 		注：忽略考虑长度大于pattern的单词
	 * @param pattern		eg: zou.hao
	 * @return				eg: zouchao
	 * TODO:.........有点懵逼
	 */
	public Iterable<String> keysThatMatch(String pattern) {
		Queue<String> queue = new Queue<String>();
		collection(root, "", pattern, queue);
		return queue;
	}
	
	public void collection(Node<Value> x, String pre, String pattern, Queue<String> q) {
		int d = pre.length();
		if (x == null)	return;
		int l = pattern.length();
		if (l == d && x.val != null)	q.enqueue(pre);
		if (l == d)	return;				//没找到
		char next = pattern.charAt(d);
		for (int c = 0; c < R; c ++) {
			if (next=='.' || next==c) {
				collection(x.next[c], pre+c, pattern, q);
			}
		}
	}
  
	public static void main(String[] args) {
		TrieST<Integer> st = new TrieST<>();
		st.put("zouchao", 10);
	}

}
